In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. (...) In all of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings. (shrink)

In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

In [5], Metakides and Nerode introduced the study of recursively enumerable substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel (...) [10] for Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2. (shrink)

In this paper, we study the lower semilattice of NP-subspaces of both the standard polynomial time representation and the tally polynomial time representation of a countably infinite dimensional vector space V∞ over a finite field F. We show that for both the standard and tally representation of V∞, there exists polynomial time subspaces U and W such that U + V is not recursive. We also study the NP analogues of simple and maximal subspaces. We show that the existence of (...) P-simple and NP-maximal subspaces is oracle dependent in both the tally and standard representations of V∞. This contrasts with the case of sets, where the existence of NP-simple sets is oracle dependent but NP-maximal sets do not exist. We also extend many results of Nerode and Remmel concerning the relationship of P bases and NP-subspaces in the tally representation of V∞ to the standard representation of V∞. (shrink)

Gelfond and Lifschitz proposed the notion of a stable model of a logic program. We establish that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has at least one stable model, is Σ11-complete. Due to the equivalences established in the authors' (...) previous nonmonotone rule systems papers ), this applies equally to truth maintenance systems and default logics. (shrink)

A universal Horn sentence in the language of polynomial-time computable combinatorial functions of natural numbers is true for the natural numbers if, and only if, it is true for PETs of p-time p-isolated sets with functions induced by fully p-time combinatorial operators.

A number of nonmonotonic reasoning formalisms have been introduced to model the set of beliefs of an agent. These include the extensions of a default logic, the stable models of a general logic program, and the extensions of a truth maintenance system among others. In [13] and [16], the authors introduced nonmonotomic rule systems as a nonlogical generalization of all essential features of such formulisms so that theorems applying to all could be proven once and for all. In this paper, (...) we extend Rieter's normal default theories, which have a number of the nice properties which make them a desirable context for belief revision, to the setting of nonmonotonic rule systems. Reiter defined a default theory to be normal if all the rules of the default theory satisfied a simple syntatic condition. However, this simple syntatic condition has no obvious analogue in the setting of nonmonotonic rule systems. Nevertheless, an analysis of the proofs of the main results on normal default theories reveals that the proofs do not rely on the particular syntactic form of the rules but rather on the fact that all rules have a certain consistency property. This led us to extend the notion of normal default theories with respect to a general consistency property. This extended notion of normal default theories, which we call Forward Chaining normal , is easily lifted to nonmonotomic rule systems and hence applies to general logic programs and truth maintenance. (shrink)

In a recent article (Inquiry, Vol. 19 [1976]), J. W. Meiland addresses the issue of psychologism in logic, which holds that logic is a branch of psychology and that logical laws (such as the Principle of Non?Contradiction) are contingent upon the nature of the mind. Meiland examines Husserl's critique of psychologism, argues that Husserl is not convincing, and offers two new objections to the psychologistic thesis. In this paper I attempt to rebut those objections. In question are the acceptable criteria (...) for determining the possibility or impossibility of systems of logic significantly different from our own. I argue that a criteriological application of our accepted laws of logic to this question commits a circular fallacy. I then argue that, even if we accept logical consistency as a criterion for possibility, a plausible argument for the possibility of valid alternative logics can be constructed by using the functionalist analogy between minds and automata. Finally, I attempt to rebut the claim that in logic the only changes possible are conceptual changes that would not permit a proposition to be both true and false. (shrink)

Some philosophers suspect that the functionalist account of mind supports a psychologistic account of logic. One who has argued for a connection of this kind is Remmel T. Nunn. If the connection holds, it might be a powerful support for the currently unfashionable position of psychologism; conversely, it might be a damaging objection to functionalism. In either case, to estabjish the connection would be an achievement of considerable philosophic interest.

An overview of the latest interdisciplinary research on human morality, capturing moral sensibility as a sophisticated integration of cognitive, emotional, and motivational mechanisms. Over the past decade, an explosion of empirical research in a variety of fields has allowed us to understand human moral sensibility as a sophisticated integration of cognitive, emotional, and motivational mechanisms shaped through evolution, development, and culture. Evolutionary biologists have shown that moral cognition evolved to aid cooperation; developmental psychologists have demonstrated that the elements that underpin (...) morality are in place much earlier than we thought; and social neuroscientists have begun to map brain circuits implicated in moral decision making. This volume offers an overview of current research on the moral brain, examining the topic from disciplinary perspectives that range from anthropology and neurophilosophy to justice and law. The contributors address the evolution of morality, considering precursors of human morality in other species as well as uniquely human adaptations. They examine motivations for morality, exploring the roles of passion, extreme sacrifice, and cooperation. They go on to consider the development of morality, from infancy to adolescence; findings on neurobiological mechanisms of moral cognition; psychopathic immorality; and the implications for justice and law of a more biological understanding of morality. These new findings may challenge our intuitions about society and justice, but they may also lead to more a humane and flexible legal system. Contributors Scott Atran, Abigail A. Baird, Nicolas Baumard, Sarah Brosnan, Jason M. Cowell, Molly J. Crockett, Ricardo de Oliveira-Souza, Andrew W. Delton, Mark R. Dadds, Jean Decety, Jeremy Ginges, Andrea L. Glenn, Joshua D. Greene, J. Kiley Hamlin, David J. Hawes, Jillian Jordan, Max M. Krasnow, Ayelet Lahat, Jorge Moll, Caroline Moul, Thomas Nadelhoffer, Alexander Peysakhovich, Laurent Prétôt, Jesse Prinz, David G. Rand, Rheanna J. Remmel, Emma Roellke, Regina A. Rini, Joshua Rottman, Mark Sheskin, Thalia Wheatley, Liane Young, Roland Zahn. (shrink)

This paper discusses an extension of Answer Set Programming called Hybrid Answer Set Programming which allows the user to reason about dynamical systems that exhibit both discrete and continuous aspects. The unique feature of Hybrid ASP is that it allows the use of ASP type rules as controls for when to apply algorithms to advance the system to the next position. That is, if the prerequisites of a rule are satisfied and the constraints of the rule are not violated, then (...) the algorithm associated with the rule is invoked. (shrink)

An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...) of languages is just the set of e such that Pe has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language. (shrink)

The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...) the method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs. (shrink)

Recent studies indicate that mammalian chromosomes contain discretecis‐acting loci that control replication timing, mitotic condensation, and stability of entire chromosomes. Disruption of the large non‐coding RNA gene ASAR6 results in late replication, an under‐condensed appearance during mitosis, and structural instability of human chromosome 6. Similarly, disruption of the mouse Xist gene in adult somatic cells results in a late replication and instability phenotype on the X chromosome. ASAR6 shares many characteristics with Xist, including random mono‐allelic expression and asynchronous replication timing. (...) Additional “chromosome engineering” studies indicate that certain chromosome rearrangements affecting many different chromosomes display this abnormal replication and instability phenotype. These observations suggest that all mammalian chromosomes contain “inactivation/stability centers” that control proper replication, condensation, and stability of individual chromosomes. Therefore, mammalian chromosomes contain four types ofcis‐acting elements, origins, telomeres, centromeres, and “inactivation/stability centers”, all functioning to ensure proper replication, condensation, segregation, and stability of individual chromosomes. (shrink)

This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, then the group (...) is recursively isomorphic to a polynomial-time group with universe A being the set of tally representations of natural numbers Tal = s{;1s};* or the set of binary representations of the natural numbers Bin. We also construct a recursive Abelian group with all elements of finite order but which has elements of arbitrary large finite order which is not isomorphic to any polynomial-time group with universe Tal or Bin. Similar results are obtained for structures , where f is a permutation on the set A. (shrink)